This invention relates to communication networks, and more particularly, to hop-by-hop routing in which different network nodes have different views of the network topology.
Networks are the principal means of exchanging or transferring information, which may be in the form of data, voice, text, video and the like, among different communication devices connected to the network(s), including I/O devices such as computer terminals, multimedia workstations, fax machines, printers, servers, telephones, videophones, and the like. A network typically comprises switching nodes connected to each other and to communication devices by communication links. Each link is characterized by link capacity, available bandwidth, link propagation delay, processing delay at the associated node, delay variation, and loss probability, among other things. Such characteristics are referred to as xe2x80x9cmetrics,xe2x80x9d with some remaining constant, and others varying over time. Information input from the communication devices to the network may be in any form, but is often formatted into packets of either fixed or variable length. When information is to be exchanged between two communication devices, a path is established within the network connecting the nodes (called a source node and destination node) with which those devices are associated.
In many networks, a given communications stream between a specified source and destination is carried over a set of physical paths (i.e., paths comprising the source and destination nodes, and possibly one or more intermediate nodes, and communication links connecting the included nodes) within the network. An important element of network design is the process of selecting a set of physical paths for routing information through the network. This process may take into account various factors, such as network topology, currently available network resources, and quality of service (QoS) commitments made to network users, e.g., guaranteed bandwidth or maximum packet delay, among others. To support path selection, different network nodes maintain information about the network, including node adjacency and link incidence, reachability of different nodes, as well as various other link metrics. This information is stored in a so-called xe2x80x9ctopology databasexe2x80x9d of the node and constitutes the node""s view of the network.
The routing of information packets from a source node to any other node in the network or a segment of the network, in which all nodes have the same view of the network topology is well established. Two existing routing paradigms in such networks are source routing and hop-by-hop routing. In source routing, the entire route taken by a packet from source to destination may be pre-computed and placed on the packet. As the packet is passed from the first node to a second node, the second node strips its address from the pre-specified route and passes the packet to the next node indicated in the packet header. In the alternative routing technique of hop-by-hop routing, no pre-computed route is employed. Each packet contains only the destination address. Upon receiving a packet, each intermediate node refers to its routing table, computed on the basis of its topology database, to forward the packet along the next hop towards the destination node.
Well-known methods, such as Dijkstra""s shortest path algorithm, have been developed, which given the single static view of the network, determine under fairly general conditions the shortest routing path between any two network nodes. However, if different network nodes have different views of the network topology, such algorithms cannot guarantee loop-free and effective routing.
Recently, the focus in network routing has shifted, however, toward dynamic or state-adaptive routing. Beside reducing configuration work, such routing adapts quickly to changes in the available resources of the network and link failures. Several design solutions exist for dynamic routing in computer networks and are still under development, with distance vector and link-state protocol approaches being the ones well-known.
The basic idea of link state routing protocols is that each node sends local network topology information to its neighbors. This information is then propagated through the network using sophisticated xe2x80x9cfloodingxe2x80x9d mechanisms. As the result, every node accumulates the view of the entire network in its topology database. The generation and flooding of information is repeated each time a node sees a significant change in available local resources. The distributed pieces of topology information, link state up-dates (LSU) or link state elements (LSE), carry a unique identifier and a version number increasing when the information inside of such an LSU is changing. Additionally, to prevent this process from being triggered too often, a dampening function controls the thresholds holding back non-significant changes. The topology database resulting from the execution of this latter xe2x80x9cfloodingxe2x80x9d mechanism between nodes is used to compute routes to the desired destinations. Such routes are used, for example, in hop-by-hop forwarding of packets. The distance vector approach is based on a significantly different idea. Each node continuously diffuses information about the distances to different network sites reachable via that node. At the same time, it uses data received from other nodes and metrics of its own links to recompute the set of best routes, thus updating the distance information it distributes.
Despite the simplicity of the latter protocols, they are plagued by problems, such as long convergence times, forming of loops and lack of scalability in terms of topology sizes supported. Research is being performed to alleviate some of the problems. It should be noted that these link-state protocols also suffer from excessive amount of information being flooded in larger topologies. Therefore, newer link-state routing protocols incorporate a concept of xe2x80x9chierarchy,xe2x80x9d where a part of the network running a link-state protocol collapses into a logical node in the view of distant nodes, and between such logical nodes, sometimes called areas, where some form of distance vector protocol is being executed.
Modern routing protocols, such as PNNI, are following the trend toward extensibility for future requirements, which abandon fixed packet formats and use TLV (type, length, value)xe2x80x94encoded packet schemes. The xe2x80x9ctypexe2x80x9d describes the fixed part of the TLV transmitted and the xe2x80x9clengthxe2x80x9d indicates the offset in the packet where the next TLV starts. In cases where the length exceeds the length of the fixed part of the TLV, embedded TLVs are present. Generally, TLV encoded packets transferring topology information in modern routing protocols can be interpreted as representations of lists of arbitrary elements embedded themselves in a recursive fashion into lists at a higher level.
An additional property of many of the prior art routing protocols is their ability to flood information elements even if they are opaque to the receiver since their type is not known. This allows newer protocol versions to be introduced as well as experimental features in an existing network to be deployed without the necessity of bringing all the nodes synchronously to the same release. To operate properly, guaranteeing packet delivery to the destination without creating loops, the link-state and distance vector protocols require that the topology databases of different network nodes converge to the same view of the network. In the networks deployed so far, however, different versions of link-state protocols cannot interoperate when new metrics or novel link properties are introduced, unless a translation between them is performed. Furthermore, network topologies are traditionally partitioned into disjoint domains corresponding to different routing protocols due to the possibility of loop creation.
The present invention presents a method to effect hop-by-hop routing in a network segment where different nodes have different views of the network topology. In particular, the methods of this invention are applicable when each node in a network or network segment may be aware of only a subset of the communication links in the network, without perceiving other communication links. Based on each node""s individual view of the network, the method introduces the concept of a visibility set that includes all visible communication links. A network segment may contain an ordered hierarchy of such visibility sets and each visibility set may contain a subset of all communication links in the network segment.
In general, an efficient algorithm is disclosed for searching for a family of one-to-all optimal feasible paths in a communication network where different nodes may have different views of the network topology. Generally, the invention comprises the following steps:
(a) restricting the set of available paths to a destination node to the set of feasible paths from the source node to the destination node; and
(b) choosing as the optimal route the feasible path which has the lowest cost, wherein a path is a feasible path if (i) the path does not contain a cycle, and (ii) for each intermediate node visited by the path, the subpath from that intermediate node to the destination node is visible from the intermediate node.
The invention ensures that forwarding a packet along an optimal feasible path guarantees its eventual delivery to the destination node without being dropped or being routed to the same node twice. The present method provides for the execution of multiple dynamic routing protocols, possibly overlaying each other in the same address space, within a network with common kinds of metrics of arbitrary complexity. It also solves the problem of interoperability when new metrics or novel link properties are being introduced and eliminates the necessity to run different protocols and protocol versions within disjoint routing domains.